//
// Created by dgy on 2022/12/10.
//
#include "iostream"
using namespace std;
class Node{
public:
    int val;
    Node *next;
    Node *random;
    Node(int _val){
        val=_val;
        next=NULL;
        random=NULL;
    }
};
class Solution{
public:
    Node* copyRandomList(Node* head){
        if (head==NULL)
            return NULL;
        Node *copy;
        copy=(Node*)malloc(sizeof(Node));
        copy->val=head->val;
        copy->random=head->random;
        Node *p=head;
        Node *q,*s;
        s=copy;
        p=p->next;
        while (p!=NULL){
            q=(Node*)malloc(sizeof(Node));
            q->val=p->val;
            q->random=p->random;
            q->next=s->next;
            p=p->next;
        }
        return copy;
    }
};
